﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Intrinsics.Arm;
using System.Text;
using System.Threading.Tasks;

class Sol42
{

    public int Trap2(int[] height)//暴力法，两次循环
    {
        int[] vol = new int[height.Length];//数组存放每个柱子存放的水

        int len=height.Length;

        if (len < 3)//少于三个柱子，肯定存不住
        {
            return 0;
        }

        for (int i = 0; i < len; i++)
        {//分别计算每一个位置的水柱高度
            int leftH = i;
            int rightH= i;
            //先找一下左右最高的柱子
            //1，找左边的
            for(int left = i; left >= 0; left--)
            {
                if(height[left] > height[leftH])
                {
                    leftH = left;
                }
                   
            }  
            //2，找右边的
            for(int right = i; right <len; right++)
            {
                if(height[right] > height[rightH])
                {
                    rightH = right;
                }
                   
            }
            //Console.WriteLine("第"+i+"个柱子，左边最高的是：第    "+ leftH+ "   个柱子，左边最高的是：   "+ rightH);
           


            //当前柱子和左右的最高柱子有下面的三种关系
            //1，中间比两边低---找左右比较低的
            if (height[i] < height[rightH] && height[i] < height[leftH])
            {
                if(height[rightH]< height[leftH])
                {
                    vol[i] = height[rightH] - height[i];
                }
                else
                {
                    vol[i] = height[leftH] - height[i];
                }


            }
            else
            {//2,中间的比两边任意一边高(等于也不行）

                vol[i] = 0;

            }
            




        }
        int sum = 0;
        //累计所有的vol
        for(int j=0; j<height.Length; j++)
        {

            sum += vol[j]; }
        return sum;
    }


    public int Trap3(int[] height)//动态规划
    {
        

        int len = height.Length;
        if (len ==0)//少于三个柱子，肯定存不住
        {
            return 0;
        }
        int[] leftH = new int[len];//数组存放每个柱子左边的最高柱子
        int[] rightH = new int[len];//数组存放每个柱子右边的最高柱子


        leftH[0] = height[0];
        for(int i=1; i<len; i++)
        {
            leftH[i] =Math.Max(leftH[i-1],height[i]);//存的时候会和当前柱子的高度比较，所有不会出现比中间的低的情况
        }
        rightH[len - 1] = height[len - 1];
        for (int i= len - 2; i>=0; i--)
        {
            rightH[i] =Math.Max(rightH[i+1],height[i]);
        }
        int sum = 0;
        
        for (int i = 0; i < len; i++)
        {
            Console.WriteLine("第" + i + "个柱子，左边最高的是：第    " + leftH[i] + "   个柱子，右边最高的是：   " + rightH[i]);
            int vol = 0;
            if (height[i] < rightH[i] && height[i] < leftH[i])
            {
                
                if (rightH[i] < leftH[i])
                {
                    vol = rightH[i] - height[i];
                }
                else
                {
                    vol = leftH[i] - height[i];
                }


            }
            else
            {//2,中间的比两边任意一边高(等于也不行）

                vol = 0;

            }
            Console.WriteLine(vol);
            sum += vol;
        }
        return sum;

    }

    public int Trap(int[] height)//双指针法
    {

        int len= height.Length;
        int left=0;
        int right= len - 1;
        int leftH = 0;
        int rightH = 0;
        int sum = 0;

        while (left < right)
        {
            leftH = Math.Max(leftH, height[left]);//更新一波
            rightH = Math.Max(rightH, height[right]);//更新一波

            if (height[left] < height[right])//计算一波，
            {
                

                sum += leftH-height[left];//必须计算较小的
                left++;//只有移动left才可能导致，height[left] 》 height[right]，然后更新
            }
            else
            {
                
                sum += rightH - height[right];
                right--;
            }

        }

        return sum;

    }


    }

    class Program42
{
    static void Main42(string[] args)
    {
        int[] height = { 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 };
        //int[] height = { 4, 2, 0, 3, 2, 5 };

        Sol42 sol = new Sol42();
        int res = sol.Trap(height);
        Console.WriteLine("一共接"+res);
        Console.ReadKey();
    }
}
